package jzoffer;

/**
 * Author:   dengxin
 * Date:     2020/6/12 9:39 下午
 * 变态跳台阶
 * 青蛙可以一次跳上1/2/3/4/..../n-1/n级台阶，求该青蛙跳上一个n级台阶共有多少种跳法
 */
@SuppressWarnings("all")
public class jz9 {

    /**
     * 递归，青蛙跳上第n级台阶存在n种情况，从第0/1/2/3/.../n-2/n-1阶台阶跳上第n阶
     * 即f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)+f(0)
     * 显然f(0)=f(1)=1
     * f(2)=f(0)+f(1)=2,f(3)=f(2)+f(1)+f(0)=2*f(2),f(4)=f(3)+f(2)+f(1)+f(0)=2*f(3)
     * f(n)=2*f(n-1)=2^2*f(n-2)=2^(n-2)*f(2)=2^(n-1)
     */
    
    private static int jump(int n) {
        if (n==0 || n==1) {
            return 1;
        }
        return (int)Math.pow(2,n-1);
    }
    
}
